Modern computer systems allow multiple processes (e.g. software programs) to run simultaneously on a central processing unit (CPU). These processes store and retrieve information from memory within the computer system. This memory is accessed by means of a physical address, i.e., an absolute coordinate system by which individual memory locations are identified. In the interests of efficient memory allocation and for the ease of software design, individual processes are not allocated the physical addresses of the physical memory. Rather, individual processes are allocated a virtual address representing the portion of the memory resources which are available to that process. The total allocated virtual addresses (the virtual address space) may represent a larger space than the actual physical memory, allowing individual processes to operate as if more memory than the actual physical memory is present in the computer system.
A memory management unit (MMU) mediates between the virtually addressed memory accesses requested by each process and the physical addresses of the available physical memory storing the desired data. An MMU is a device or circuit that supports virtual memory and paging by translating virtual addresses into physical addresses. Each process running in a system with an MMU receives a portion of a virtual address space. Typically, the virtual address space is divided into pages of 2N bits each, each process receiving a number of pages. Each virtual address accessed by a process running on the CPU is split into a virtual page number (VPN), comprising the most significant bits of the virtual address, and an offset within that page, comprising the N least significant bits of the virtual address. Thus, if an address is 32 bits and a page size is 4 KB (2N=212), then the page offset is defined as the rightmost (least significant) 12 bits (N) of the address and the virtual page number is defined as the remaining (most significant) 20 bits in the 32 bit virtual address.
The MMU contains a page table that is indexed by the virtual page number. While the offset is left unchanged by the MMU, the virtual page number is mapped through the page table to a physical page number (PPN). Each page table entry (PTE) has a stored virtual page number and a corresponding physical page number. The page table provides a physical page number corresponding to a stored virtual page number matching an applied virtual page number. This physical page number is recombined with the page offset to create a physical address, which is an actual location in physical memory (e.g. RAM). For example, with an 8 bit address and a 4 bit (22) page size, the most significant 4 bits of a virtual address are the virtual page number and the least significant 4 bits are the page offset. A particular process generates a first address including a first virtual page number, which is applied to a page table of an MMU. Through the page table lookup, the MMU determines a first physical page number from the virtual page number for the particular process. The page offset (least significant 4 bits) is combined with this first physical page number to generate a physical address of a location in memory.
To save time in translating virtual page numbers to physical page numbers, the most recently used page translations may be cached in a translation look-aside buffer (TLB). Translation look-aside buffers typically have an associative memory, with comparators for each word, so that the translation can be retrieved in one clock cycle. If the virtual page number is not found in the translation look-aside buffer, then the MMU page table is checked for the virtual page number. A typical translation look-aside buffer has four cached page translations. For some applications, a virtual address is calculated from the sum of two operands. As a result, the translation of a virtual address to a physical address first requires calculation of the virtual page number from the most significant bits of the sum of the two operands, and then requires translation by a translation look-aside buffer or page table to a physical address.
FIG. 1 is a block diagram of a conventional system 100 for the calculation of a physical address from two 32 bit operands. An adder 110 receives a first 32 bit operand OPA and a second 32 bit operand OPB, combining them to form a virtual page number VPN_IN and a page offset PO. A translation look-aside buffer 120 includes four rows and two columns, each row in the first column storing a virtual page number (e.g. VPNs 130, 131, 132, and 133) and the corresponding row in the second column storing a physical page number (e.g. PPNs 140, 141, 142, and 143). For example, the first row in translation look-aside buffer 120 contains a virtual page number 130 and a corresponding physical page number 140. Thus, translation look-aside buffer 120 maps an applied virtual page number matching virtual page number 130 to a physical page number physical page number 140. In this example, translation look-aside buffer 120 provides matching physical page number 140 as a physical page number PPN_OUT.
The page offset PO generated from the sum of operands OPA and OPB is concatenated with physical page number PPN_OUT to generate a physical address. Specifically, translation look-aside buffer 120 receives virtual page number VPN_IN and compares virtual page number VPN_IN to each of VPNs 130, 131, 132, and 133. If virtual page number VPN_IN matches one of VPNs 130-133, translation look-aside buffer 120 provides the corresponding one of PPNs 140, 141, 142, and 143 as PPN_OUT. A concatenator 115 combines page offset PO with physical page number PPN_OUT to generate the physical address PA.
The process of adding 32 bit numbers and then applying them to a translation look-aside buffer takes a certain amount of time. Because the addition of operands OPA and OPB (e.g. a 32 bit addition) within adder 110 occurs in a sequential fashion, the overall time taken to determine a physical address from a virtual address is delayed by the amount of time taken to complete the serial addition of the operands prior to their comparison to the cached VPNs. Additionally, adder 110, which can accommodate 32 bit operands OPA and OPB, requires a large amount of circuit area. Hence, it would be desirable to reduce the amount of time and space required to produce a physical address from a virtual address formed by two operands.